package 热题100.普通数组.最大子数组和_53_中等;
/*
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：
输入：nums = [1]
输出：1

示例 3：
输入：nums = [5,4,-1,7,8]
输出：23

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
思路：
    现在的大小与前一位有关，滑动窗口无法维护，因为前后指针的逻辑不明，无法按照一个规则进行移动，所以考虑动态规划。
    转移规则就是，nums[i] 单独成为一段还是加入 f(i−1) 对应的那一段，这取决于 nums[i] 和 f(i−1)+nums[i] 的大小，
    我们希望获得一个比较大的，于是可以写出这样的动态规划转移方程：f(i)=max{f(i−1)+nums[i],nums[i]}
* */
public class Solution {
    public static void main(String[] args) {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        int[] nums1 = {-1,-2};
        int[] nums2 = {5,4,-1,7,8};
        System.out.println(maxSubArray(nums1));
    }
    public static int maxSubArray(int[] nums) {
        // ans为答案，初始化为nums的第一个数， f(i)为状态转移的函数，表示到i为止的最大和
        // 转移函数为 f(i - 1) + w(i) 与 值本身的大小 w(i)， 当前数是加入f值更大还是自己本身更大
        int ans = nums[0], f = 0;
        for (int t : nums){
            f = Math.max(f + t, t);
            ans = Math.max(f, ans);
        }
        return ans;
    }
}
